P4606 [SDOI2018]战略游戏

发表于

闲扯

1
2
3
4
圆方树上圆方果，
圆方树下你和我。
圆方树前建虚树，
欢乐多又多

题面

P4606 [SDOI2018]战略游戏

Solution

这个题的题意很明显。

给出一个连通图，每次选择几个点作为关键点，问有几个除关键点之外的点，满足将该点及其周围的边去掉后，存在两个关键点 $u,v$ 不再连通。

我们有个很显然的想法，将包含这几个关键点的子图取出来，问其中有几个割点。

直接做显然没什么想法，但是我们可以建出这个图的圆方树。

然后，问题就变成了求包含这几个点的子图中有几个圆点，这个可以把点按照 $dfn$ 升序排序之后，通过差分快速求解。

因为有 $\sum|S|\leq 2\times 10^5$ ，我们可以用虚树来解决。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
using namespace std;
template<class T>il read(T &x){
	int f=1;char k=getchar();x=0;
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=(x<<3)+(x<<1)+k-'0';
	x*=f;
}
template<class T>il _print(T x){
	if(x/10) _print(x/10);
	putchar(x%10+'0');
}
template<class T>il print(T x){
	if(x<0) putchar('-'),x=-x;
	_print(x);
}
ll mul(ll a,ll b,ll mod){long double c=1.;return (a*b-(ll)(c*a*b/mod)*mod)%mod;}
it qpow(int x,int m,int mod){
	int res=1,bas=x;
	while(m){
		if(m&1) res=(1ll*res*bas)%mod;
		bas=(1ll*bas*bas)%mod,m>>=1;
	}
	return res;
}
const int MAXN = 1e5+5;
int T,n,m,q,k,u,v,head[MAXN<<1],num_edge,hd[MAXN<<1],num,ver;
struct Edge{
	int next,to;
	Edge(){}
	Edge(int next,int to):next(next),to(to){}
}edge[MAXN<<2],ed[MAXN<<2];
il add_edge(int u,int v){
	edge[++num_edge]=Edge(head[u],v),head[u]=num_edge;
	edge[++num_edge]=Edge(head[v],u),head[v]=num_edge;
}
il add(int u,int v){
	ed[++num]=Edge(hd[u],v),hd[u]=num;
	ed[++num]=Edge(hd[v],u),hd[v]=num;
}
int dfn[MAXN<<1],low[MAXN],stk[MAXN],top,cnt;
il Tarjan(int u){
	low[u]=dfn[u]=++cnt,stk[++top]=u;
	for(ri i=head[u];i;i=edge[i].next){
		if(!dfn[edge[i].to]){
			Tarjan(edge[i].to);
			low[u]=min(low[u],low[edge[i].to]);
			if(low[edge[i].to]==dfn[u]){
				++ver;
				for(ri x=0;x!=edge[i].to;--top){
					x=stk[top];
					add(ver,x);
				}
				add(ver,u);
			}
		}
		else
			low[u]=min(low[u],dfn[edge[i].to]);
	}
}
int dep[MAXN<<1],f[MAXN<<1][20],dis[MAXN<<1];
il DFS(int u,int fa){
	dfn[u]=++cnt,dep[u]=dep[fa]+1;
	f[u][0]=fa,dis[u]=dis[fa]+(u<=n);
	for(ri i=1;i<=18;++i)
		f[u][i]=f[f[u][i-1]][i-1];
	for(ri i=hd[u];i;i=ed[i].next){
		if(ed[i].to==fa)
			continue;
		DFS(ed[i].to,u);
	}
}
it LCA(int u,int v){
	if(dep[u]<dep[v])
		swap(u,v);
	for(ri i=18;i>=0;--i)
		if(dep[f[u][i]]>=dep[v])
			u=f[u][i];
	if(u==v)
		return u;
	for(ri i=18;i>=0;--i)
		if(f[u][i]!=f[v][i])
			u=f[u][i],v=f[v][i];
	return f[u][0];
}
int val[MAXN<<1];
inl bool cmp(int x,int y){
	return dfn[x]<dfn[y];
}
il Solve(){
	read(n),read(m);
	del(head,0),num_edge=0,del(hd,0),num=0;
	for(ri i=1;i<=m;++i)
		read(u),read(v),add_edge(u,v);
	del(dfn,0),cnt=0,top=0,ver=n;
	Tarjan(1);
	cnt=0,DFS(1,0);
	read(q);
	for(ri i=1;i<=q;++i){
		read(k);
		for(ri j=1;j<=k;++j)
			read(val[j]);
		sort(val+1,val+1+k,cmp);
		int ans=-2*k;
		for(ri j=1;j<=k;++j){
			u=val[j],v=val[j%k+1];
			ans+=dis[u]+dis[v]-2*dis[LCA(u,v)];
		}
		if(LCA(val[1],val[k])<=n)
			ans+=2;
		print(ans/2),puts("");
	}
}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(T);
	for(ri i=1;i<=T;++i)
		Solve();
	return 0;
}